圖解LeetCode(入門篇): 125. Valid Palindrome

16th鐵人賽

zaleyu

2024-09-07 07:40:11

196 瀏覽

分享至

125. Valid Palindrome

題目描述:
一個字串如果在將所有大寫字母轉換為小寫字母並移除所有非字母數字的字符後，正反讀起來相同，則稱為Palindrome(回文)。字母數字字符包括字母和數字。

給定一個字串 s，如果它是回文則返回 true，否則返回 false。

Example:

Input: s = "race a car"
Output: false
Explanation: "raceacar"不是palindrome。

解題思路:
判斷回文最簡單的解法是使用雙指針，從字串的頭和尾開始，逐個字符向內比較，直到兩個指針相遇。如果在比較過程中有不同的字符，則表示不是回文。因為題目給的輸入可能包含空格或其他非字母數字的字符，所以在進行比較之前，必須先移除這些字符，並將所有字母轉為小寫，然後再開始進行比對。

var isPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        while (left < right && !isAlphaNumeric(s[left])) {
            left++;
        }
        while (left < right && !isAlphaNumeric(s[right])) {
            right--;
        }
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        left++;
        right--;
    }

    return true;
};

function isAlphaNumeric(c) {
    return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}

時間複雜度：O(n)，其中 n 是字串的長度。我們最多會遍歷整個字串一次來移除非字母數字字符，並使用雙指針進行比較。
空間複雜度：O(1)，除了少量額外的變數用來存儲指針和字符外，演算法不需要額外的空間。

還記得 LeetCode 的第 9 題 Palindrome Number 嗎？這題其實和那題非常相似，我們也可以利用 JavaScript 提供的內建 API 來更快速地解答。步驟如下：

首先，我們使用正則運算式replace(/[^a-zA-Z0-9]/g, '')來移除字串中所有非字母數字的字符。[^a-zA-Z0-9]表示匹配任意不是字母或數字的字符，而g代表全局替換，意思是會替換字串中所有符合條件的字符。還有別忘了使用toLowerCase()來轉成小寫字符串。
移除完不需要的字符後，我們接著將字串分成兩半 (s1 和 s2)。如果字串的長度是奇數，則需要調整後半部分 s2 的起始點，因為回文比較的過程中，中間的字符可以略過，這是因為在回文中，中間的字符本身不影響對稱性（例如字串 "aca" 的 c 不需要比較）。
之後，將後半部分的字串 s2 使用split('')轉換成陣列，並用reverse()方法反轉字符的順序。
最後，使用join('')將反轉後的陣列重新連接成一個字串，然後與前半部分的字串 s1 進行比較。如果兩者相等，那麼這個字串就是回文。

透過這樣的方式，我們能夠簡單且快速地判斷字串是否為回文，而不需要自己寫雙指針進行比較。

var isPalindrome = function(s) {
    s = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();

    let mid = Math.floor(s.length / 2);
    let s1 = s.substring(0, mid);
    let s2 = s.substring(s.length % 2 === 0 ? mid : mid + 1).split('').reverse().join('');

    return s1 === s2;
};

時間複雜度：O(n)，其中 n 是字符串的長度。我們需要遍歷字串兩次，一次用於正則替換，另一次則是進行字串的分割、反轉和比較操作。
空間複雜度：O(n)，因為需要額外的空間來儲存處理後的字串及其反轉結果。

對於這道題，我們可以將其歸類為「Two Pointers」和「array.reverse」這兩個分類。雙指針技巧是在解 LeetCode 的各種題目中非常常見的解法，尤其在處理字符串或陣列時，能夠有效地縮減時間複雜度。雙指針從兩端同時進行比較的過程，不僅簡單易懂，還能在不增加額外空間的情況下提高效率。

然而，從開發者的日常工作角度來看，選擇使用內建的 API 通常會更加高效且易於維護。比如使用 JavaScript 的 replace() 來過濾非字母數字字符，再使用 reverse() 來反轉字串，這樣不僅代碼可讀性強，也能減少出錯的機會。並且這種做法時間複雜度相差不大，更能節省開發時間，尤其在處理較為簡單的問題時，使用 API 是一個很好的選擇。

在 LeetCode 題目中，靈活運用雙指針等基本算法的技巧很重要，但同時，了解並掌握各種內建函數和 API 也能在實際開發中提升工作效率。因此，建議讀者在練習算法的同時，也應注意學習如何高效地運用現成的工具來解決問題，這樣能在不同的情境中選擇最適合的解法。